//求二叉树的深度和宽度

// #include "BiTNode.h"  在下面那个链队头文件中已经导入了，为防止重复导入，这里就注释掉了
#include "LinkQueue.h"
#include <iostream>

using namespace std;

int GetDepth(BiTree T) //递归求二叉树的深度(只有根节点算深度为1)
{
    if (T == nullptr) //若树为空，则返回0
        return 0;
    else
        return GetDepth(T->lchild) > GetDepth(T->rchild) ? (GetDepth(T->lchild) + 1) : (GetDepth(T->rchild) + 1); //如果当前结点的 左子树的深度 比 右子树的深度 要 深 则返回 左子树的深度+1；否则返回 右子树的深度+1
}

int GetWidth(BiTree T) //求二叉树的宽度(具有最多结点数的那一层的 结点数)【BFS】 【一层一层的处理，这个思想很重要，要注意到辅助队列的特性及该如何利用】
{
    if (T == nullptr) //若树为空，则返回0
        return 0;
    int lastLevelWidth = 0; //记录上一层的宽度(结点数)
    int tempLevelWidth = 0; //复制一份上一层的宽度用于计算
    int curLevelWidth = 0;  //记录当前层的宽度
    int nWidth = 0;         //二叉树的宽度
    LinkQueue Q;            //辅助队列Q
    InitQueue(Q);           //初始化队列Q
    EnQueue(Q, T);          //把二叉树根节点压入队列，此时第一层遍历完毕(只有根节点)
    lastLevelWidth = 1;     //更新上一层宽度
    BiTNode *p = nullptr;   //用于承接队列中的二叉树结点
    while (!IsEmpty(Q))     //队列不为空，就一直执行
    {
        for (tempLevelWidth = lastLevelWidth; tempLevelWidth != 0; tempLevelWidth--) //将上一层的结点一次弹出并压入队列
        {
            DeQueue(Q, p);            //出队并赋值给p
            if (p->lchild != nullptr) //把当前结点的左孩子压入队列
                EnQueue(Q, p->lchild);
            if (p->rchild != nullptr) //把当前结点的右孩子压入队列
                EnQueue(Q, p->rchild);
        }
        curLevelWidth = GetQueueSize(Q);                          //更新当前层的宽度为当前队列的长度
        nWidth = nWidth < curLevelWidth ? curLevelWidth : nWidth; //若当前层的宽度比当前树的宽度大，则更新树的宽度
        lastLevelWidth = curLevelWidth;                           //更新上一层的宽度为当前层的宽度，以便后续操作
    }
    return nWidth;
}

int main()
{
    //二叉树T的初始化
    BiTree T = (BiTNode *)malloc(sizeof(BiTNode));
    InitT1(T); //初始化为ExampleTree1;

    //测试代码
    // cout << GetDepth(T);
    cout << GetWidth(T);
    return 0;
}